package leetcode_801_900;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class LeeCode_827 {
    public static void main(String[] args) {
        System.out.println(largestIsland(new int[][]{{0, 0}, {0, 0}}));
        System.out.println(largestIsland(new int[][]{{1, 1}, {1, 0}}));
    }
    private static int largestIsland(int[][] grid) {
        int n = grid.length;
        int[] p = new int[n * n];
        for (int i = 0; i < n * n; i++) {
            p[i] = i;
        }
        int[][] dirs = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1){
                    for (int[] dir : dirs) {
                        int x = dir[0] + i, y = dir[1] + j;
                        if (x < 0 || x >= n || y < 0 || y >= n)
                            continue;
                        if (grid[x][y] == 1){
                            union(p, i * n + j, x * n + y);
                        }
                    }
                }
            }
        }
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n * n; i++) {
            int r = find(p, i);
            int x = i / n, y = i % n;
            if (grid[x][y] == 0){
                map.put(r, 0);
                continue;
            }
            map.put(r, map.getOrDefault(r, 0 ) + 1);
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0){
                    Set<Integer> rs = new HashSet<>();
                    for (int[] dir : dirs) {
                        int x = i + dir[0], y = j + dir[1];
                        if (x < 0 || x >= n || y < 0 || y >= n)
                            continue;
                        rs.add(find(p, x * n + y));
                    }
                    int count = 1;
                    for (Integer r : rs) {
                        count += map.get(r);
                    }
                    ans = Math.max(ans, count);
                }
            }
        }
        return ans == 0 ? n * n : ans;
    }
    private static int find(int[] p, int x){
        if (p[x] != x)
            p[x] = find(p, p[x]);
        return p[x];
    }
    private static void union(int[] p, int x, int y){
        int rx = find(p, x);
        int ry = find(p, y);
        p[rx] = ry;
    }
}